This invention relates to automatic reclamation of allocated, but unused memory, or garbage, in a computer system that uses a generational garbage collector and, particularly, to techniques for selectively allocating objects in younger or older generations used by the garbage collector. Memory reclamation may be carried out by a special-purpose garbage collection algorithm that locates and reclaims memory that is unused, but has not been explicitly de-allocated. There are many known garbage collection algorithms, including reference counting, mark-sweep, mark-compact and generational garbage collection algorithms. These, and other garbage collection techniques, are described in detail in a book entitled “Garbage Collection, Algorithms for Automatic Dynamic Memory Management” by Richard Jones and Raphael Lins, John Wiley & Sons, 1996.
However, many of the aforementioned garbage collection techniques often lead to long and unpredictable delays because normal processing must be suspended during the garbage collection process (called “stop the world” or STW processing) and these collectors at least occasionally scan the entire heap. The garbage collection process is performed by collection threads that perform collection work when all other threads are stopped. Therefore, they are generally not suitable in situations, such as real-time or interactive systems, where non-disruptive behavior is of greatest importance.
Conventional generational collection techniques alleviate these delays somewhat by concentrating collection efforts on a small memory area, called the “young” generation, in which most of the object allocation activity occurs. Since many objects allocated in the younger generation do not survive to the next collection, they do not significantly contribute to the collection delay. In addition, the more frequent collection of the young generation reduces the need for collecting the remaining large memory area, called the “old” or “mature” generation and, thus, reduces the overall time consumed during garbage collection.
“Pre-tenuring” is a technique that increases the efficiency of generational garbage collection by identifying object allocations likely to produce objects with longer-than-average lifetimes, and allocating such objects directly in the old generation. This selective allocation fills the young generation with objects with shorter-than-average lifetimes, decreasing their survival rates and increasing the efficiency of collection.
A key issue in pre-tenuring is identifying the object allocations to be allocated in the old generation. One approach is offline profiling in which program training runs are conducted with selected data in order to predict the behavior of subsequent “real” program runs. This approach has the advantage of allowing relatively extensive program “instrumentation” to aid in the prediction, but requires that the user perform extra work, and that the training runs accurately predict the behavior of subsequent “real” runs.
Another approach is static analysis conducted during compilation, such as just-in-time compilation. This static analysis examines object allocation “sites” or instructions that allocate new objects. For example, it has been proposed that an allocation of an object from an allocation site followed by an assignment of that object to a static variable, leads to the conclusion that an object allocated from that allocation site is a good candidate for pre-tenuring. See, for example, “Understanding the Connectivity of Heap Objects”, M. Hirzel, J. Henkel, A. Diwan and M. Hind, Proceedings of the Third International Symposium on Memory Management, June 2002. Another technique combines static analysis with dynamic techniques to allocate an object in the same generation as an existing object into which a reference to the newly allocated object is assigned. See “Finding Your Cronies: Static Analysis for Dynamic Object Colocation”, S. Guyer and K. McKinley, ACM Conference on Object-Oriented Systems, Languages and Applications, 2004
Still another approach is to perform profiling used to make pre-tenuring decisions dynamically on the running program. This approach requires no extra effort on the part of users, and the training program run is the real program run, but the cost of the profiling must be very small, or else it will outweigh any efficiency advantages that might be gained. Therefore, techniques using this approach generally use some form of sampling, in which the lifetimes of only a subset of allocated objects are tracked. If this subset is large enough, it will gather enough information to permit accurate pre-tenuring decisions. But the subset cannot be too large, or else the expense of tracking the sampled objects will be too high. Examples of conventional sampling techniques are disclosed in “Dynamic Adaptive Pre-Tenuring”, T. Harris, Proceedings of the Second International Symposium on Memory Management, October, 2000 and “Dynamic Object Sampling for Pre-tenuring”, M. Jump, S. M. Blackburn, and K. S. McKinley, ACM International Symposium on Memory Management, October 2004. Rather than sampling all allocations directly, both of these techniques use an event, such as the allocation of a new local allocation buffer, to identify an allocation to be sampled.
However, these conventional sampling techniques are vulnerable to “sampling bias.” In particular, the allocations of larger objects often cause a local allocation buffer to overflow and, thus, require a new local allocation buffer to be allocated. Therefore, techniques that sample objects based on their allocation from new local allocation buffers tend to sample larger objects.